/**
 * @a https://leetcode.cn/problems/course-schedule-ii/
 */

#include "../../common.h"

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges;
        vector<int> in_degree(numCourses);

        for(auto& edge:prerequisites){
            int dst = edge[0], src = edge[1];
            edges[src].push_back(dst);
            ++in_degree[dst];
        }

        // queue<int> que;
        // vector<int> ret;
        // for(int i = 0; i < numCourses; ++i){
        //     if(in_degree[i] == 0)
        //     {
        //         que.push(i);
        //         ret.push_back(i);
        //     }
        // }
        // while(que.size()){
        //     int out = que.front(); que.pop();
        //     for(int dst : edges[out]){
        //         --in_degree[dst];
        //         if(in_degree[dst] == 0)
        //         {
        //             que.push(dst);
        //             ret.push_back(dst);
        //         }
        //     }
        // }

        queue<int> que;
        for(int i = 0; i < numCourses; ++i){
            if(in_degree[i] == 0)
            {
                que.push(i);
            }
        }
        vector<int> ret;
        while(que.size()){
            int out = que.front(); que.pop();
            ret.push_back(out);
            for(int dst : edges[out]){
                --in_degree[dst];
                if(in_degree[dst] == 0)
                {
                    que.push(dst);
                }
            }
        }
        // for(int isPositive : in_degree){
        //     if(isPositive) return {};
        // }
        if(ret.size() != numCourses) return {};
        return ret;
    }
};